package com.demo.排序算法.test;

import cn.hutool.core.lang.Console;

/**
 * @author 86130
 */
public class Other {

    public static void main(String[] args) {
        寻找一个数组中的最大值();
        递归求小和问题();
        逆序对问题();
        荷兰国旗问题();
    }

    private static void 寻找一个数组中的最大值() {
        int[] arr = {1, 8, 89, 75, 2, 45, 66, 2};
        Console.log("递归寻找最大值 数组是{}, 最大值为: {}", arr, getMax(arr, 0, arr.length - 1));
    }

    private static int getMax(int[] arr, int s, int e) {
        if (s == e) {
            return arr[s];
        }
        int mid = e + ((s - e) >> 1);
        return Math.max(getMax(arr, s, mid), getMax(arr, mid + 1, e));
    }

    private static void 递归求小和问题() {
        // 小和指
        // 0 + (1) + (1 + 4) + (1 + 4 + 5) + (1) + (1 + 2) = 20
        int[] a = {1, 4, 5, 6, 2, 3};
        Console.log("递归求小和问题, 数组是: {}, 小和为: {}", a, getCount(a, 0, a.length - 1));
    }

    private static int getCount(int[] a, int s, int e) {
        if (s == e) {
            // 不产生小和
            return 0;
        }
        int mid = e + ((s - e) >> 1);
        return getCount(a, s, mid) + getCount(a, mid + 1, e) + smallCountMerge(a, s, mid, e);
    }

    private static int smallCountMerge(int[] a, int s, int mid, int e) {
        int[] help = new int[e - s + 1];
        int i = 0;
        int p1 = s;
        int p2 = mid + 1;
        // 小和
        int smallCount = 0;

        // 都不越界的情况
        while (p1 <= mid && p2 <= e) {
            // 左边比右边小 产生小和
            smallCount += a[p1] < a[p2] ? a[p1] * (e - p2 + 1) : 0;
            // 做成排序的数组
            help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
        }

        while (p1 <= mid) {
            help[i++] = a[p1++];
        }

        while (p2 <= e) {
            help[i++] = a[p2++];
        }

        // 排序
        for (i = 0; i < help.length; i++) {
            a[s + i] = help[i];
        }

        return smallCount;
    }

    private static void 逆序对问题() {
        int[] a = {5, 56, 45, 23, 78, 1, 5, 6};
        // 打印逆序对
        // (5 1) (56 45) (56 23) (56 1) (56 5) (56 6) (45 23) (45 1) (45 5) (45 6) (23 1) (23 5) (23 6) (78 1) (78 5) (78 6)
        nixudui(a, 0, a.length - 1);
    }
    private static void nixudui(int[] a, int s, int e) {
        if (s == e) {
            return;
        }
        int mid = s + ((e - s) >> 1);
        nixudui(a, s, mid);
        nixudui(a, mid + 1, e);
        nixuduiMerge(a, s, mid, e);
    }

    // 打印
    private static void nixuduiMerge(int[] a, int s, int mid, int e) {
        int p1 = s;
        int p2 = mid + 1;
        int[] help = new int[e - s + 1];
        int i = 0;

        // 不越界的情况
        while (p1 <= mid && p2 <= e) {
            if (a[p1] > a[p2]) {
                for (int t = 0; t < (e - p2 + 1); t ++) {
                    Console.log("逆序对({}, {})", a[p1], a[p2 + t]);
                }
            }
            help[i++] = a[p1] > a[p2] ? a[p1++] : a[p2++];
        }
        while (p1 <= mid) {
            help[i++] = a[p1++];
        }

        while (p2 <= e) {
            help[i++] = a[p2++];
        }

        // 排序
        for (i = 0; i < help.length; i++) {
            a[s + i] = help[i];
        }
    }

    // 荷兰国旗问题
    private static void 荷兰国旗问题() {
        // 给定一个数 如 8 将小于8的放左边 等于的放中间  大于的放右边
        int tmp = 8;
        int[] a = {87, 1, 6, 56, 8, 5, 4, 0, 8, 7, 9, 56, 0, 8};
        int t = -1;
        int s = a.length;
        Console.log("荷兰国旗问题: 原={}", a);
        for (int i = 0; i < s; ) {
            if (a[i] < tmp) {
                swap(a, ++t, i++);
            } else if (a[i] > tmp) {
                swap(a, --s, i);
            } else {
                i++;
            }
        }
        Console.log("荷兰国旗问题: 现={}", a);
    }

    private static void swap(int[] array, int i, int j) {
        if (i < array.length && j < array.length && i != j) {
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }
}
